//
// Created by Senhai Xu on 2025/3/10.
//
//BM10 两个链表的第一个公共结点
#include <iostream>
#include <unordered_set>
using namespace  std;
struct ListNode {
        int val;
        struct ListNode *next;
        ListNode(int x) :
                        val(x), next(NULL) {
        }
};
class Solution {
public:
  ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        std::unordered_set<ListNode*> myset;
        while(pHead1!=nullptr){
            myset.insert(pHead1);
            pHead1=pHead1->next;
        }
        while(pHead2!=nullptr){
            if(myset.find(pHead2)!=myset.end()){
                return pHead2;
            }
            pHead2=pHead2->next;
        }
        return nullptr;
  }
  ListNode* FindFirstCommonNode2( ListNode* pHead1, ListNode* pHead2) {
        ListNode* p1 = pHead1;
        ListNode* p2 = pHead2;
        while(p1!=p2){
            p1 = (p1==nullptr)?pHead2:p1->next;
            p2 = (p2==nullptr)?pHead1:p2->next;
        }
        return p1;
  }
  
};